package com.接雨水;

import java.util.Stack;
/*
 * 遇到2002这种的时候
 * 当      2 0 0 2
 * index   0 1 2 3
 * 当index=2的时候坑是形成不了 的，会进入下一次循环将index=1弹出这时候，才会有左边界和右边界来形成一个坑
 * */
class Solution {
    public int trap(int[] height) {
        if(height.length<3)return 0;
        int result=0;
        Stack<Integer> s = new Stack<Integer>();//stack中存放水平坐标方便等下的运算
        int i=0;
        while(i<height.length){
            if(s.isEmpty()||height[i]<=height[s.peek()]){
                s.push(i++);
            }
            else{
                int temp=s.pop();//栈顶元素当做坑
                if(s.isEmpty()){
                    continue;
                }
                else{//s.peek()<temp
                    int left = height[s.peek()];//此时的栈顶元素就是左边界
                    int right = height[i];//比较的元素就是右边界
                    int min = Math.min(left,right);
                    int area = (min-height[temp])*(i-s.peek()-1);
                    result=result+area;
                }
            }
        }
        return result;
    }
}
